import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

class Solution {

    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{2,0},{1,0},{3,1},{3,2},{1,3}};
        System.out.println(canFinish(numCourses, prerequisites));
    }

    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int[] p: prerequisites) {
            List<Integer> l = map.getOrDefault(p[0], new LinkedList<Integer>());
            l.add(p[1]);
            map.put(p[0], l);
        }
        
        LinkedList<Integer> stack = new LinkedList<>();
        boolean[] visited = new boolean[2000];
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            HashSet<Integer> path = new HashSet<>();
            int key = entry.getKey();
            if (visited[key]) {
                continue;
            }else{
                path.add(key);
                stack.push(key);
                visited[key] = true;
            }
            while (!stack.isEmpty()) {
                if (!path.contains(key)) {
                    path.add(key);
                    stack.push(key);
                    visited[key] = true;
                }

                boolean flag = true;
                if (map.containsKey(key)) {
                    for (Integer i: map.get(key)){
                        if (path.contains(i)) {
                            return false;
                        }
                        if (!visited[i]){
                            key = i;
                            flag = false;
                            break;
                        }
                    }
                }

                if (flag) {
                    path.remove(key);
                    stack.pop();
                    if (!stack.isEmpty()) {
                        key = stack.peek();
                    } else {
                        break;
                    }
                }
            }
        }
        return true;
    }

    // TODO recursion
}